/**
给你一个非负整数数组 nums 和一个整数 target 。 

 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 

 
 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 
 

 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 

 

 示例 1： 

 
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
 

 示例 2： 

 
输入：nums = [1], target = 1
输出：1
 

 

 提示： 

 
 1 <= nums.length <= 20 
 0 <= nums[i] <= 1000 
 0 <= sum(nums[i]) <= 1000 
 -1000 <= target <= 1000 
 

 Related Topics 数组 动态规划 回溯 👍 1999 👎 0

*/
package editor.cn;

import java.util.Arrays;

class Solution494{
    public static void main(String[] args) {
        Solution solution = new Solution494().new Solution();
        int[] nums=new int[]{1};
        System.out.println(solution.findTargetSumWays(nums,1));
        //System.out.println(solution.findTargetSumWays(nums, 1));
        //System.out.println(Solution.count);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //static int count=0;
        public int findTargetSumWays(int[] nums, int target) {
        int sum= Arrays.stream(nums).sum();
        int space=(sum+target)>>1;
        if (sum<Math.abs(target)||(sum+target)%2==1)return 0;

    //    x+y=sum
    //    x-y=target
    //    x=(sum+target)/2
    //    x一定是偶数，那么就简单了。 dp[j]表示装满背包容量为j的背包的方法数量。
    //    也可以使用回溯，不知道会不会超时。试一试。

    //    这里是组合。组合是固定的写法。求的是方案数量。————>就是组合。
    //    return Dp(nums);
    //    return Dp(nums, space);
        int count=0;
        Arrays.sort(nums);
        return backTraceing(nums,space,0,0,count);
    }


        //使用回溯法来做
        //为什么这里[0000000]不行。
        private int backTraceing(int[] nums, int space, int startIndex, int sum, int count) {
            if (sum==space){
                count++;
                return count;
            }
            for (int i = startIndex; i < nums.length; i++) {
             if (sum+nums[i]>space)break;
             sum+=nums[i];
            count= backTraceing(nums,space,i+1,sum, count);
             sum-=nums[i];
            }
            return count;
        }

        //使用dp来做
        private int Dp(int[] nums, int space) {
            int[] dp = new int[space+1];
            dp[0]=1;//一定要这样初始化，不然就全是0；//可以理解成就是不装，那就只有一种(全部都不装，)
            for(int i = 0; i< nums.length; i++){
                // 遍历背包，求的是方案数，记住递推公式
                for(int j = space; j>= nums[i]; j--){
                    dp[j]+= dp[j- nums[i]];//装进来容量j的物品的方法数量，等于之前的dp[j]加上本轮加入nums[i]的方法数。其实记住就好，这就是一维dp的变种
                //
                }
            }
            return dp[space];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}












